
/*
Date:20210429 11:17pm
key:完全模仿大神。
    错误:一开始按照数组最后一个值初始化了一个bool dp，实际上那些没有石头的就不能跳到，根本不用遍历那些。因此只需要在石头数组里遍历即可。
    反思:首先怎么想到是二维dp？老以为是dp[i]就能表示能不能跳到，确定的k才是只有三种可能，实际上不同的k造就的dp[i]往后面又有无数种。应该是i与k联合表示其中一种可能是否成立，故二维dp[i][k];
    先插一个memset函数，他能初始化一片内存，只需要指针头 数值 偏移量(大小)
    这里又是嵌套两层i,j.保证i以前的i，k都能被刷新。对于每两个元素，差值决定跳数，再检查跳数k与i有没有合理。
*/

class Solution {
public:
bool f[2021][2021];
    bool canCross(vector<int>& stones) {
        memset(f,false,sizeof f);
        int n = stones.size();
        if(stones[1] != 1) return false;
        f[1][1] = true;
        for(int i = 2;i < n; i++){
            for(int j = 1; j < i; j++){
                int k = stones[i] - stones[j];
                if(k <= j + 1) f[i][k] = f[j][k - 1] || f[j][k] || f[j][k + 1];
            }
        }
        for(int i = 1; i < n; i++){
            if(f[n - 1][i]) return true;
        }
        return false;
    }
};
